import java.util.Arrays;
import java.util.Comparator;

/**
 * @program: LeetCode
 * @description: LeetCode : 1005. K 次取反后最大化的数组和
 * @author: WXY
 * @create: 2023-01-20 16:42
 * @Version 1.0
 **/
public class Num1005_largestSumAfterKNegations {
    public static int largestSumAfterKNegations(int[] arr, int k) {
        Integer[] nums = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Math.abs(o2) - Math.abs(o1);
            }
        });

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        //现在到这里，只有两种情况了，一是全正了，但是k还有，二是k没有了，
        //如果k还剩余，数组又是全正的，K是偶数不影响，k是奇数就将最小的数反转
        if (k % 2 == 1) nums[nums.length - 1] = -nums[nums.length - 1];
        int ans = 0;
        for (int num : nums) {
            ans += num;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, -1, 5, -4};
        int sum = largestSumAfterKNegations(arr, 4);
        System.out.println(sum);
    }
}
